/*
题目链接：https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/
题目：1011.在D天内送达包裹的能力
提交时间：2024.9.16
二分，运载最小值
*/

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        auto check = [&](long long m) ->bool{     
            int d=1;      //当包裹加到最后一天时，对应天数不会加1，此时只能初始值为1开始计算
            int w=0;
            for(auto x:weights){
                if(w+x>m){           //不用考虑相等的情况，直接在大于的时候加1已经考虑到了相等的情况
                    d++;
                    w=0;
                }
                w+=x;
            }
            return d<=days;         //当运输时间小于所给的时间，说明最低运载能力可以更小
        };
        int l=0;    //下界，每次运最大重量的包裹
        int r=0;     //上界，一次运完所有包裹
        for(int i=0;i<weights.size();i++) {r+=weights[i];l=max(l,weights[i]);}   
        while(l<r){
            int mid=l+(r-l)/2;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        return l;
    }
};